/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: user
 * Date: 2023-10-19
 * Time: 17:15
 */
import java.util.*;
public class Test {

    public static void main8(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);

        int x = stack.pop();
        System.out.println(x);

        int x2 = stack.peek();
        System.out.println(x2);

        x2 = stack.peek();
        System.out.println(x2);

        stack.pop();
        stack.pop();
        //stack.pop();
        System.out.println(stack.empty());

    }

    public static void main7(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        LinkedList<Integer> list = new LinkedList<>(arrayList);

        System.out.println(list);


        LinkedList<Integer> list2 = new LinkedList<>();
        list2.add(10);//默认他是尾插法
        list2.add(20);
        list2.add(30);
        list2.add(2,19);

        System.out.println(list2);

        System.out.println("============");

        for (int x : list2) {
            System.out.print(x+" ");
        }
        System.out.println();
        System.out.println("======ListIterator======");
        ListIterator<Integer> listIterator = list2.listIterator();
        while (listIterator.hasNext()) {
            System.out.print(listIterator.next()+" ");
        }
        System.out.println();
        System.out.println("======ListIterator2======");
        ListIterator<Integer> listIterator2 = list2.listIterator(list2.size());
        while (listIterator2.hasPrevious()) {
            System.out.print(listIterator2.previous()+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(22);
        mySingleList1.addLast(32);
        mySingleList1.addLast(42);
        mySingleList1.addLast(52);
        mySingleList1.display3(mySingleList1.head);

/*
        myLinkedList.addIndex(3,888);

        myLinkedList.display();*/

    }

    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode head1,
                                                      MySingleList.ListNode head2) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newHead;
        while (head1 != null && head2 != null) {
            if(head1.val < head2.val) {
                tmp.next = head1;
                head1 = head1.next;
            }else {
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp  = tmp.next;
        }
        if(head1 != null) {
            tmp.next = head1;
        }
        if(head2 != null) {
            tmp.next = head2;
        }
        return newHead.next;
    }



    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA,
                                                            MySingleList.ListNode headB) {
        //1.求链表的长度
        MySingleList.ListNode pl = headA;//pl 永远指向 最长的链表
        MySingleList.ListNode ps = headB;//ps 永远指向 最短的链表
        int lenA = 0;
        while(pl != null) {
            lenA++;
            pl = pl.next;
        }
        //pl = null;
        int lenB = 0;
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        //ps = null;
        pl = headA;
        ps = headB;
        int len = lenA-lenB;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB-lenA;
        }
        //pl永远指向最长的链表  ps 永远指向了 最短的链表

        //2.让最长的链表 先走len步
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        //3. pl和ps  现在在相同的起始位置

        while(pl != ps ) {
            pl = pl.next;
            ps = ps.next;
        }
        //走到这里pl和ps相等了 pl == ps == null;
        if(pl == null) {
            return null;
        }
        return pl;

    }

    public static void createCut(MySingleList.ListNode headA,
                                 MySingleList.ListNode headB) {
        headB.next.next = headA.next.next;
    }

    public static void main5(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(22);
        mySingleList1.addLast(32);
        mySingleList1.addLast(42);
        mySingleList1.addLast(52);
        mySingleList1.display();

        mySingleList1.createLoop();
        System.out.println(mySingleList1.hasCycle());
        MySingleList.ListNode ret = mySingleList1.detectCycle();
        System.out.println(ret.val);
    }

    public static void main4(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(22);
        mySingleList1.addLast(32);
        mySingleList1.addLast(42);
        mySingleList1.addLast(52);
        mySingleList1.display();

        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(13);
        mySingleList2.addLast(45);
        mySingleList2.addLast(67);
        mySingleList2.addLast(89);
        mySingleList2.addLast(90);
        mySingleList2.display();

        createCut(mySingleList1.head,mySingleList2.head);
        MySingleList.ListNode ret = getIntersectionNode(mySingleList1.head,mySingleList2.head);
        System.out.println(ret.val);


        /*MySingleList.ListNode newHead =
                mergeTwoLists(mySingleList1.head,mySingleList2.head);

        mySingleList1.display(newHead);*/
    }


    public static void main3(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(1);
        mySingleList.addLast(2);
        mySingleList.addLast(3);
        mySingleList.addLast(4);
        mySingleList.addLast(5);
        mySingleList.display();//
        MySingleList.ListNode ret = mySingleList.findKthToTail(1);
        System.out.println(ret.val);
        //MySingleList.ListNode ret = mySingleList.reverseList();
        //mySingleList.display(ret);
    }


    public static void main2(String[] args) {
        MySingleList mySingleList = new MySingleList();
        //mySingleList.createList();
        mySingleList.addLast(12);
        mySingleList.addLast(23);
        mySingleList.addLast(12);
        mySingleList.addLast(12);
        mySingleList.addLast(12);
        mySingleList.display();//
        //mySingleList.addIndex(2,88888888);
        //mySingleList.removeAllKey(12);
        mySingleList.display();//
        /*System.out.println("长度："+mySingleList.size());
        System.out.println(mySingleList.contains(134));*/
        mySingleList.clear();
        System.out.println("fsafa");
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        ret.add(list1);
        //上述第一行只有1个1，已经添加到了ret当中。接下来我们需要从第2行开始计算
        for (int i = 1; i < numRows; i++) {
            //当前行
            List<Integer> curRow = new ArrayList<>();
            curRow.add(1);//一行开始的1
            //中间位置 就需要我来计算了
            List<Integer> prevRow = ret.get(i-1); //前一行
            for (int j = 1; j < i; j++) {
                int num = prevRow.get(j)+prevRow.get(j-1);
                curRow.add(j,num);
            }
            curRow.add(1);//一行结束的1
            ret.add(curRow);
        }
        return ret;
    }



}
